package com.aha.firstchapter.third;

import java.util.Arrays;

/**
 * 快速排序
 * Created by wangxin on 2015/10/27.
 */
public class QuickSort {
    int[] arr = {6,4,1,8,2,3,3,7,9,2,8};
    public static void main(String[] args) {

        QuickSort qs = new QuickSort();
        qs.start(0,qs.arr.length-1);
        System.out.println(Arrays.toString(qs.arr));
    }
    private void start(int left, int right){
        if(left > right) return;
        int temp = arr[left];
        int i = left;
        int j = right;
        while (i!=j){
            while (arr[j] >= temp && i<j) j--;
            while (arr[i] <= temp && i<j) i++;
            if (i<j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        arr[left] = arr[i];
        arr[i] = temp;
        start(left,i-1);
        start(i+1,right);
    }
    /*private void start(int[] arr,int m,int n) {

        for(int i = n-1;i>0;i--){
            if(arr[i]<arr[m]){
                for(int j = m;j<n;j++){
                    if(i==j){
                        int temp = arr[j];
                        arr[j] = arr[m];
                        arr[m] = temp;
                        //start(arr,0,j);
                        //start(arr,j+1,arr.length);
                        return;
                    }
                    if(arr[j] > arr[m] && j<i){
                        int t = arr[j];
                        arr[j] = arr[i];
                        arr[i] = t;
                        break;
                    }

                }
            }
        }
    }*/
}
